package com.mdnote.practice.binary_tree;

import com.mdnote.practice.dp.LeetCode1143;

import javax.transaction.TransactionRequiredException;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/30
 * @description 二叉树展开为链表
 */
public class LeetCode114 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        LeetCode114 leetCode114 = new LeetCode114();
        leetCode114.flatten(root);
        System.out.println(root);
    }
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        _flatter(root);
    }

    private void _flatter(TreeNode node) {
        // Terminator
        if (node == null) {
            return;
        }
        // Process
        // 处理左右子树
        _flatter(node.left);
        _flatter(node.right);
        // 左右子树已经处理好了，现在要处理当前的节点
        TreeNode left = node.left;
        TreeNode right = node.right;
        // 把left街到right
        node.left = null;
        node.right = left;
        // 把左边剩下的元素街到右边
        TreeNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }

    private static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }
}
